#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ep emplace
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

int read() {
	int x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;
using tl = tuple < int, int, int >;

const int N = 1e5 + 10;

vec G[N];
int n, tp;
vec pot;

void dfs(int x, int p, int d) {
	int cnt = 0;
	for(auto y : G[x]) if(y ^ p) dfs(y, x, d + 1), cnt++;
	if(d & 1) pot.pb(1 - cnt);
}

void solve() {
	n = in, tp = in;
	rep(i, 1, n) G[i].clear(); pot.clear();
	rep(i, 2, n) {
		int u = in, v = in;
		G[u].pb(v); G[v].pb(u);
	}
	dfs(1, 0, 1);
	if(tp == 1) {
		int res = 0;
		for(auto v : pot) res += max(v, -v);
		printf("%d\n", res);
	} else {
		int tot = 0;
		for(auto &v : pot) v = abs(v), tot += v;
		bitset < N > al;
		al.set(0);
		for(auto &v : pot) al |= al << v;
		int res = tot;
		rep(i, 0, tot) if(al.test(i)) res = min(res, abs(tot - i - i));
		printf("%d\n", res);
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	for(int T = in; T; T--) solve();
	return 0;
}
